package com.heima.leetcode.LCR;

/**
 * leetcode LCR 095. 最长公共子序列
 * @author 勾新杰
 * @version 1.0
 * @date 2024/11/11 19:11
 */
public class E095 {
    /*
          a   b   c   x   y   z  str2
      a   1   1   1   1   1   1
      b   1   2   2   2   2   2
      x   1   2   2   3   3   3
      y   1   2   2   3   4   4
      z   1   2   2   3   4   5
     str1

      这个二维动态数组的dp[i,j]表示的是str1[0] - str1[i]之间
      和str2[0] - str2[j]之间的两个子字符串的最常公共子序列

      if(i == j){
         if(i > 0 && j > 0){
            dp[i][j] = dp[i-1][j-1] + 1;
         }else{ // 第一行和第一列第一次出现后往后都是1
            dp[i][j] = 1;
         }
      }else{
         if(i > 0 && j > 0){
            dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
         }else{
            if(i == 0){
                dp[i][j] = dp[i][j-1];
            }else{
                dp[i][j] = dp[i-1][j];
            }
         }
      }

      可见这个动态方程太复杂了，优化以下动态数组的第一行和第一列，进行简化

              a   b   c   x   y   z  str2
          0   0   0   0   0   0   0
      a   0   1   1   1   1   1   1
      b   0   1   2   2   2   2   2
      x   0   1   2   2   3   3   3
      y   0   1   2   2   3   4   4
      z   0   1   2   2   3   4   5
     str1

      这个二维动态数组的dp[i,j]表示的是str1[0] - str1[i-1]之间
      和str2[0] - str2[j-1]之间的两个子字符串的最常公共子序列
      当然这个里面只有i>0 && j>0的部分才有意义，其他地方不用考虑

      if(str1[i-1] == str2[j-1]){
          dp[i][j] = dp[i-1][j-1] + 1;
      }else{
          dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
      }

      可见简单明了很多
     */

    /**
     * <h3>方法一：动态规划二维数组</h3>
     * @param text1 文本1
     * @param text2 文本2
     * @return 最长公共子序列的长度
     */
    public int longestCommonSubsequence1(String text1, String text2) {
        char[] text1Array = text1.toCharArray();
        char[] text2Array = text2.toCharArray();
        // 1. 创建动态数组
        int[][] dp = new int[text1Array.length + 1][text2Array.length + 1];
        // 2. 填充动态数组
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < text2Array.length + 1; j++) {
                if (text1Array[i - 1] == text2Array[j - 1]){
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        // 3. 返回右下角
        return dp[text1Array.length][text2Array.length];
    }

    /*
          a   b   c   x   y   z  str2
          0   0   0   0   0   0   0
      a   0   1   1   1   1   1   1
      b   0   1   2   2   2   2   2
      x   0   1   2   2   3   3   3
      y   0   1   2   2   3   4   4
      z   0   1   2   2   3   4   5
     str1

      这个二维动态数组的dp[i,j]表示的是str1[0] - str1[i-1]之间
      和str2[0] - str2[j-1]之间的两个子字符串的最常公共子序列
      当然这个里面只有i>0 && j>0的部分才有意义，其他地方不用考虑

      if(str1[i-1] == str2[j-1]){
          dp[i][j] = dp[i-1][j-1] + 1;
      }else{
          dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
      }
     */

    /**
     * <h3>方法二：动态规划一维数组</h3>
     * @param text1 文本1
     * @param text2 文本2
     * @return 最长公共子序列的长度
     */
    public int longestCommonSubsequence2(String text1, String text2) {
        char[] text1Array = text1.toCharArray();
        char[] text2Array = text2.toCharArray();
        // 1. 创建动态数组
        int[] dp = new int[text2Array.length + 1];
        // 2. 填充动态数组
        for (int i = 1; i < text1Array.length + 1; i++) {
            int lastRowPrev = 0; // j每行从1开始，所以他的上一行的prev值初始是0
            for (int j = 1; j < text2Array.length + 1; j++) {
                int temp = dp[j]; // 因为更新当前dp[j]之前要把其记录下来，作为dp[j+1]的lastRowPrev，因为处理当前dp[j]的时候会修改dp[j]的值
                if (text1Array[i - 1] == text2Array[j - 1]){
                    dp[j] = lastRowPrev + 1; // 这里不能直接用dp[j - 1]因为，dp[j- 1]肯定已经被处理过了，属于当前行的prev
                }else {
                    dp[j] = Math.max(dp[j], dp[j - 1]); // dp[j]对应上一行的当前值，dp[j - 1]对应当前行的prev值（已经修改为最新的）
                }
                lastRowPrev = temp;
            }
        }
        // 3. 返回右下角
        return dp[text2Array.length];
    }
}
